package 力扣日常刷题.木22一月.第05天0113;

/**
 * @author 帅小伙
 * @date 2022/1/13
 * @description
 */
public class Demo06回溯中等黄金矿工 {

    public int getMaximumGold(int[][] grid) {
        if (grid == null || grid.length == 0)
            return 0;
        int res = 0;
        //查找最大路径值
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                //函数dfs是以坐标(i,j)为起点，查找最大路径值
                res = Math.max(res, dfs(grid, i, j));
            }
        }
        //返回最大路径值
        return res;
    }

    public int dfs(int[][] grid, int i, int j) {
        if(i >= grid.length || i <0 || j <0 || j >=grid[0].length || grid[i][j] == 0)return 0;
        int t = grid[i][j];
        //准备深入进去
        grid[i][j] = 0;
        int up = dfs(grid,i-1,j);
        int down = dfs(grid,i+1,j);
        int right = dfs(grid,i,j+1);
        int left = dfs(grid,i,j-1);
        int max = Math.max(up,Math.max(down,Math.max(right,left)));
        // 回溯
        grid[i][j]  = t;
        return t+max;
    }

}
